package io.zouyalong.algo.leetcode;

import java.util.List;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class FullException extends Exception {}

class KContainer {
    ListNode[] entries;
    int size;
    int cap;

    KContainer(int k) {
        cap = k;
        entries = new ListNode[cap];
    }

    public ListNode pop() {
        ListNode head = new ListNode(0);
        ListNode cursor = head;
        if (this.size >= cap) {
            // 已满，反转
            for (int i = this.size-1; i>=0; i--) {
                cursor.next = this.entries[i];
                cursor = cursor.next;
                cursor.next = null;
            }
        } else {
            for (int i = 0; i < this.size; i++) {
                cursor.next = this.entries[i];
                cursor = cursor.next;
                cursor.next = null;
            }
        }
        this.size = 0;
        return head.next;
    }

    public void push(ListNode node) throws FullException {
        if (this.size >= this.cap) {
            throw new FullException();
        }
        this.entries[this.size] = node;
        this.size++;
    }
}

public class ReverseNodesInKGroup {
    public static void main(String[] args) {
        var input = new int[]{1, 2, 3, 4, 5, 6};
        int k = 2;
        var inst = new ReverseNodesInKGroup();
        var head = inst.converts(input);
        System.out.printf("Input: ");
        inst.print(head);
        var out = inst.solution2Window(head, k);
        System.out.printf("Output: ");
        inst.print(out);
    }

    public ListNode converts(int[] src) {
        var result = new ListNode(0);
        var cursor = result;
        for (int each : src) {
            cursor.next = new ListNode(each);
            cursor = cursor.next;
        }
        return result.next;
    }

    public void print(ListNode head) {
        for (ListNode cursor = head; cursor != null; cursor = cursor.next) {
            System.out.printf("%d, ", cursor.val);
        }
        System.out.println();
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        var container = new KContainer(k);
        ListNode result = new ListNode(0);
        ListNode tail = result;
        for (ListNode cursor = head; cursor != null; ) {
            try {
                container.push(cursor);
                cursor = cursor.next;
            } catch (FullException e) {
                var reversedLink = container.pop();
                tail.next = reversedLink;
                for (; tail.next != null; tail = tail.next);
            }
        }
        var remainLink = container.pop();
        tail.next = remainLink;
        return result.next;
    }

    public ListNode solution2Window(ListNode head, int k) {
        var dummy = new ListNode(0);
        dummy.next = head;
        var pre = dummy;
        var end = dummy;
        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) end = end.next;
            if (end == null) {
                break;
            }
            var start = pre.next;
            var next = end.next; // 剩下的链表
            end.next = null; // 置为 null 保证翻转不传递
            pre.next = reverse(start);
            start.next = next;// 原来的头部变成了尾部
            pre = start;
            end = pre;
        }
        return dummy.next;
    }

    public ListNode reverse(ListNode head) {
        var dummy = new ListNode(0);
        var remain = head;
        while (remain != null) {
            var current = remain;
            remain = remain.next;
            current.next = dummy.next;
            dummy.next = current;
        }
        return dummy.next;
    }
}
